#include <bits/stdc++.h>
using namespace std;

/*
2785. 将字符串中的元音字母排序
已解答
中等
相关标签
premium lock icon
相关企业
提示
给你一个下标从 0 开始的字符串 s ，将 s 中的元素重新 排列 得到新的字符串 t ，它满足：

所有辅音字母都在原来的位置上。更正式的，如果满足 0 <= i < s.length 的下标 i 处的 s[i] 是个辅音字母，那么 t[i] = s[i] 。
元音字母都必须以他们的 ASCII 值按 非递减 顺序排列。更正式的，对于满足 0 <= i < j < s.length 的下标 i 和 j  ，如果 s[i] 和 s[j] 都是元音字母，那么 t[i] 的 ASCII 值不能大于 t[j] 的 ASCII 值。
请你返回结果字母串。

元音字母为 'a' ，'e' ，'i' ，'o' 和 'u' ，它们可能是小写字母也可能是大写字母，辅音字母是除了这 5 个字母以外的所有字母。

 

示例 1：

输入：s = "lEetcOde"
输出："lEOtcede"
解释：'E' ，'O' 和 'e' 是 s 中的元音字母，'l' ，'t' ，'c' 和 'd' 是所有的辅音。将元音字母按照 ASCII 值排序，辅音字母留在原地。
示例 2：

输入：s = "lYmpH"
输出："lYmpH"
解释：s 中没有元音字母（s 中都为辅音字母），所以我们返回 "lYmpH" 。
 

提示：

1 <= s.length <= 105
s 只包含英语字母表中的 大写 和 小写 字母。
*/

// 法一
class Solution {
public:
    string sortVowels(string s) {
        // 容器存储
        vector<char> vowels;
        // lambda 的是否为元音字母
        auto isVowel = [](char c) {
            return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u' ||
                   c == 'A' || c == 'E' || c == 'I' || c == 'O' || c == 'U';
        };
        
        for (char c : s) {
            if (isVowel(c)) vowels.push_back(c);
        }

        // 非递减排序
        sort(vowels.begin(), vowels.end());
        // 结果数组重构  辅音字母保持原位，元音字母用排序后的替换
        int index = 0;
        string ans = s;
        for (int i = 0; i < ans.size(); ++i) {
            if (isVowel(ans[i])) {
                ans[i] = vowels[index++];  // 依次使用排序后的元音
            }
        }
        return ans;
    }
};

// 法二
class Solution {
    // 存储所有元音字母（大小写），用于快速判断字符是否为元音
    unordered_set<char> vowels={'a','e','i','o','u','A','E','I','O','U'};
public:
    string sortVowels(string s) {
        // cnt数组：用于统计各元音字母的出现次数
        // 大小58的原因：覆盖'A'(65)到'z'(122)的所有字符（122-65+1=58）
        // 初始值-1表示非元音，后续会将元音对应的位置初始化为0
        vector<int> cnt(58,-1);
        
        // 初始化元音字母在cnt中的位置为0（非元音保持-1）
        // 后续通过cnt[ch-'A']是否为-1可判断字符是否为元音
        for(char ch:vowels){
            cnt[ch-'A']=0;
        }
        
        // 统计每个元音字母在原字符串中的出现次数
        for(char& ch:s){
            // 若为元音（cnt[ch-'A']!=-1），则对应计数+1
            if(cnt[ch-'A']!=-1)
            cnt[ch-'A']++;
        }
        
        // 重新遍历字符串，替换元音字母为排序后的结果
        int idx=0;  // 用于遍历cnt数组，按ASCII顺序选取元音
        for(char& ch:s){
            // 若当前字符是元音（需要替换）
            if(cnt[ch-'A']!=-1){
                // 找到下一个有剩余计数的元音（按ASCII顺序）
                while(cnt[idx]<=0){
                    idx++;
                }
                // 用当前找到的元音替换原字符
                ch=(char)(idx+'A');
                // 该元音的剩余计数-1
                cnt[idx]--;
            }
            // 辅音字符保持不变，不做处理
        }
        
        return s;
    }
};